"""
图的三种基础实现
    使用 dictionary 存储边值表
    使用 list[[node_start, node_end, weight]] 存储边值表
    使用二维数组 [columns[value], rows[value]] 存储邻接矩阵
"""


class GraphDict:
    """
    使用 dictionary 存储边值表
    使用字典推导式进行初始化，初始化后有：
        M_Num_Of_Nodes  : 顶点个数
        M_Nodes         : 顶点集
        M_Directed      : 是否有向
        M_Adj_List      : 边值表
    """

    def __init__(self, num, directed=True):
        """
        初始化图
        :param num: 顶点个数
        :param directed: 是否有向(默认有)
        """
        self.M_Num_Of_Nodes = num
        self.M_Nodes = range(self.M_Num_Of_Nodes)
        self.M_Directed = directed
        self.M_Adj_List = {node: set() for node in self.M_Nodes}

    def Add_Edge(self, node_start, node_end, weight):
        """
        添加指定的边值。
        添加tuple(终点，边值)到value:set()中。
            # 只有可哈希hashable的对象才能加入set()
            # list等是不可哈希的，无法加入set()
        对无向图会添加相应的反向边
        :param node_start: 起始点
        :param node_end:   终止点
        :param weight:     边权值
        """
        if self.M_Directed:
            self.M_Adj_List[node_start].add((node_end, weight))
        else:
            self.M_Adj_List[node_end].add((node_start, weight))

    def Print_Edge_List(self):
        print(self.M_Adj_List)


class GraphList:
    """
    使用 list[[node_start, node_end, weight]] 存储边值表
    初始化后有：
        M_Num_Of_Nodes  : 顶点个数
        M_Directed      : 是否有向
        M_List_Of_edges : 边值表
    """

    def __init__(self, num_of_node: int, directed=True):
        """
        初始化图
        :param num_of_node: 顶点个数
        :param directed: 是否有向(默认有)
        """
        self.M_Num_Of_Node = num_of_node
        self.M_Directed = directed
        self.M_List_Of_edges = []

    def Add_edge(self, node_start, node_end, weight=1):
        """
        添加指定的边值
        对无向图会添加相应的反向边
        :param node_start:  起始点
        :param node_end:    终止点
        :param weight:      边权值
        """
        if self.M_Directed:
            self.M_List_Of_edges.append([node_start, node_end, weight])
        else:
            self.M_List_Of_edges.append([node_end, node_start, weight])

    def Print_Edge_List(self):
        """
        打印边值表
        """
        print("The edge list of graph:\n[Start, End, weight]")
        for x in self.M_List_Of_edges:
            print(x)


class GraphMatrix:
    def __init__(self, num_of_nodes, directed=True):
        """
        传入节点数、默认有向图
        初始化二维矩阵作为邻接矩阵
        :param num_of_nodes:
        :param directed:
        """
        self.M_Num_Of_Nodes = num_of_nodes
        self.M_Directed = directed
        self.M_Adj_MaTrix = [[0 for columns in range(self.M_Num_Of_Nodes)],
                             [0 for rows in range(self.M_Num_Of_Nodes)]]

    def Add_edges(self, node_start, node_end, weight=1):
        """
        添加边值
        :param node_start:  起始点
        :param node_end:    终止点
        :param weight:      边权值
        :return:
        """
        self.M_Adj_MaTrix[node_start][node_end] = weight
        if not self.M_Directed:
            self.M_Adj_MaTrix[node_end][node_start] = weight

    def Print_Adj_Matrix(self):
        """
        打印邻接矩阵
        """
        print("[", self.M_Adj_MaTrix[0])
        for i in range(1, self.M_Num_Of_Nodes - 1):
            print(" ", self.M_Adj_MaTrix[i])
        print(" ", self.M_Adj_MaTrix[self.M_Num_Of_Nodes - 1], "]")


test_graph_Dict = GraphDict(5, False)
test_graph_Dict.Add_Edge(1, 3, 4)
test_graph_Dict.Add_Edge(4, 2, 3)
test_graph_Dict.Print_Edge_List()
print()
test_graph_doubly_list = GraphList(4, True)
test_graph_doubly_list.Add_edge(0, 1, 10)
test_graph_doubly_list.Add_edge(0, 2, 6)
test_graph_doubly_list.Add_edge(0, 3, 5)
test_graph_doubly_list.Add_edge(1, 3, 15)
test_graph_doubly_list.Add_edge(2, 3, 4)
test_graph_doubly_list.Print_Edge_List()
print()
test_graph_matrix = GraphMatrix(5)
test_graph_matrix.M_Adj_MaTrix = [[0, 2, 0, 6, 0],
                                  [2, 0, 3, 8, 5],
                                  [0, 3, 0, 0, 7],
                                  [6, 8, 0, 0, 9],
                                  [0, 5, 7, 9, 0]]
test_graph_matrix.Print_Adj_Matrix()

# 输出结果：
# {0: set(), 1: set(), 2: {(4, 3)}, 3: {(1, 4)}, 4: set()}
#
# The edge list of graph:
# [Start, End, weight]
# [0, 1, 10]
# [0, 2, 6]
# [0, 3, 5]
# [1, 3, 15]
# [2, 3, 4]
#
# [ [0, 2, 0, 6, 0]
#   [2, 0, 3, 8, 5]
#   [0, 3, 0, 0, 7]
#   [6, 8, 0, 0, 9]
#   [0, 5, 7, 9, 0] ]
